import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-11-17
 * Time: 0:31
 */

//面试题 08.06. 汉诺塔问题
public class Demo {
    //方法一：
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }

    private void dfs(List<Integer> x, List<Integer> y, List<Integer> z,int n){
        //递归出口,只有一个盘子的时候，把x柱子上的盘子直接放到z柱子上
        if(n == 1) {
            z.add(x.remove(x.size()-1));
            return;
        }

        //任意一个子问题的具体步骤
        dfs(x,z,y,n-1);//借助中间的z柱子，把x柱子上的n-1个盘子放到，y柱子上
        z.add(x.remove(x.size()-1));//把x柱子的第一个剩下的盘子，放到z柱子
        dfs(y,x,z,n-1);//借助X柱子，把y柱子上的n-1个盘子，放到z柱子上
    }

    //面试方法：
    // public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    //     //不讲伍德方法
    //     for(int x : A) C.add(x);
    // }
}
